#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

// 有一组整数，请挑选出一组数字，让它们的和等于给定的值，存在打印，不存在不打印

vector<int> pickVec;
size_t pickSum{}, remainSum{}, cnt{};

void fun1(int *arr, int i, int len, int val)
{
    if (i == len)
    {
        cnt++;
        if (pickSum == val)
        {
            for (int i : pickVec)
            {
                printf("%d ", i);
            }
            printf("\n");
        }
    }
    else
    {
        pickVec.push_back(arr[i]);
        pickSum += arr[i];
        fun1(arr, i + 1, len, val);
        pickVec.pop_back();
        pickSum -= arr[i];

        fun1(arr, i + 1, len, val);
    }
}

void fun2(int *arr, int i, int len, int val)
{
    if (i == len)
    {
        cnt++;
        if (pickSum == val)
        {
            for (int i : pickVec)
            {
                printf("%d ", i);
            }
            printf("\n");
        }
    }
    else
    {
        remainSum -= arr[i];
        // 修剪左子树：只有选择数字的和小于指定值的时候，才继续找
        if (pickSum < val)
        {
            pickVec.push_back(arr[i]);
            pickSum += arr[i];
            fun2(arr, i + 1, len, val);
            pickVec.pop_back();
            pickSum -= arr[i];
        }

        // 修剪右子树：只有当已选择的数字与未来还能选择的数字的和加在一起大于等于给定值
        if (pickSum + remainSum >= val)
        {
            fun2(arr, i + 1, len, val);
        }

        remainSum += arr[i];
    }
}

void fun3(int *arr, int i, int len, int val)
{
    if(val == 0){
        for(int num: pickVec){
            printf("%d ", num);
        }
        printf("\n");
    }else{
        for(size_t idx{i}; idx < len; idx++){
            if(val >= arr[idx]){
                pickVec.push_back(arr[idx]);
                fun3(arr, idx + 1 , len, val - arr[idx]);
                pickVec.pop_back();
            }
        }
    }

    /* if(i >= len || val < pickSum)
        return; 

    pickSum += arr[i];
    pickVec.push_back(arr[i]);

    if(pickSum == val){
        for(int i: pickVec){
            printf("%d ", i);
        }
        printf("\n");
    }
    i++;
    fun3(arr, i, len, val, sum);
    i--;
    pickVec.pop_back();
    pickSum -= arr[i]; */
}

int main(int args, char *argv[])
{
    int arr[] = {4, 1, 3, 2};
    int len = sizeof(arr) / sizeof(int);

    fun3(arr, 0, len, 3);

    /* fun1(arr, 0, len, 28);
    printf("fun1的叶子节点个数：%d\n", cnt);
    for(size_t i{}; i < len; i++){
        remainSum += arr[i];
    } */
    // fun2(arr, 0, len, 14);
    // printf("fun2的叶子节点个数：%d\n", cnt);

    return 0;
}